home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / agrep / bitap.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  5KB  |  158 lines
  1. /* Copyright (c) 1991 Sun Wu and Udi Manber.  All Rights Reserved. */
  2. /* if the pattern is not simple fixed pattern, then after preprocessing */
  3. /* and generating the masks, the program goes here. four cases:  1.     */ 
  4. /* the pattern is simple regular expression and no error, then do the   */
  5. /* matching here.  2. the pattern is simple regular expression and      */
  6. /* unit cost errors are allowed: then go to asearch().                  */
  7. /* 3. the pattern is simple regular expression, and the edit cost is    */
  8. /* not uniform, then go to asearch1().                                  */
  9. /* if the pattern is regular expression then go to re() if M < 14,      */
  10. /* else go to re1()                                                     */
  11. /* input parameters: old_D_pat: delimiter pattern.                      */
  12. /* fd, input file descriptor, M: size of pattern, D: # of errors.       */
  13.  
  14. #include "agrep.h"
  15.  
  16. extern unsigned Init1, D_endpos, endposition, Init[], Mask[], Bit[];
  17. extern int DELIMITER, FILENAMEONLY, D_length, I, AND, REGEX, JUMP, INVERSE; 
  18. extern char D_pattern[];
  19. extern int TRUNCATE, DD, S;
  20. extern char Progname[], CurrentFileName[];
  21. extern int num_of_matched;
  22.  
  23. /* bitap dispatches job */
  24.  
  25. bitap(old_D_pat, Pattern, fd, M, D)
  26. char old_D_pat[], *Pattern;  int fd, M, D;  
  27. {
  28. char c;  
  29. register unsigned r1, r2, r3, CMask, i;
  30. register unsigned end, endpos, r_Init1;
  31. register unsigned D_Mask;
  32. int  ResidueSize , FIRSTROUND, lasti, print_end, j, num_read;
  33. int  k;
  34. char buffer[Max_record+Max_record+BlockSize];
  35.   D_length = strlen(old_D_pat);
  36.   for(i=0; i<D_length; i++) if(old_D_pat[i] == '^' || old_D_pat[i] == '$')
  37.                                old_D_pat[i] = '\n';
  38.   if (REGEX) { 
  39.       if (D > 4) {
  40.           fprintf(stderr, "%s: the maximum number of erorrs allowed for full regular expression is 4\n", Progname);
  41.           exit(2);
  42.       }
  43.       if (M <= SHORTREG) { re(fd, M, D);   /* SUN: need to find a even point */ 
  44.                      return; }
  45.       else { re1(fd, M, D); 
  46.              return; }
  47.   }   
  48.   if (D > 0 && JUMP == ON) 
  49.      { asearch1(old_D_pat, fd, D); return; }
  50.   if (D > 0) 
  51.      { asearch(old_D_pat, fd, D); return; }
  52.   if(I == 0) Init1 = 037777777777;
  53.  
  54.   j=0;
  55.   lasti = Max_record;
  56.   buffer[Max_record-1] = '\n';
  57.   r_Init1 = Init1;
  58.   r1 = r2 = r3 = Init[0];
  59.   endpos = D_endpos;
  60.   
  61.   buffer[Max_record-1] = '\n';
  62.   D_Mask = D_endpos;
  63.   for(i=1 ; i<D_length; i++) D_Mask = (D_Mask << 1) | D_Mask;
  64.   D_Mask = ~D_Mask;
  65.   FIRSTROUND = ON;
  66.  
  67.   while ((num_read = fill_buf(fd, buffer + Max_record, Max_record)) > 0)
  68.   {
  69.     i=Max_record; end = Max_record + num_read; 
  70.     if(FIRSTROUND) {  i = Max_record - 1 ;
  71.  
  72.             if(DELIMITER) {
  73.                 for(k=0; k<D_length; k++) {
  74.                     if(old_D_pat[k] != buffer[Max_record+k])                         break;
  75.                 }
  76.                 if(k>=D_length) j--;
  77.             }
  78.  
  79.                       FIRSTROUND = OFF;  }
  80.     if(num_read < BlockSize) {
  81.                       strncpy(buffer+Max_record+num_read, old_D_pat, D_length);
  82.                       end = end + D_length;
  83.                       buffer[end] = '\0';
  84.     }
  85.     while (i < end)
  86.     {
  87.         c = buffer[i++];
  88.         CMask = Mask[c];
  89.               r1 = r_Init1 & r3;
  90.               r2 = (( r3 >> 1 ) & CMask) | r1;
  91.         if ( r2 & endpos ) {
  92.            j++;
  93.            if(((AND == 1) && ((r2 & endposition) == endposition)) ||                           ((AND == 0) && (r2 & endposition)) ^ INVERSE )
  94.                { 
  95.                  if(FILENAMEONLY) {
  96.                     num_of_matched++;
  97.                     printf("%s\n", CurrentFileName);
  98.                     return; }
  99.                  print_end = i - D_length - 1;
  100.                  if(!(lasti >= Max_record+num_read - 1))
  101.                     output(buffer, lasti, print_end, j); 
  102.                }
  103.            lasti = i - D_length; 
  104.            TRUNCATE = OFF;
  105.            r2 = r3 = r1 = Init[0];
  106.            r1 = r_Init1 & r3;
  107.            r2 = ((( r2 >> 1) & CMask) | r1 ) & D_Mask;
  108.         }
  109.         c = buffer[i++];
  110.         CMask = Mask[c];
  111.               r1 = r_Init1 & r2;
  112.               r3 = (( r2 >> 1 ) & CMask) | r1; 
  113.         if ( r3 & endpos ) {
  114.            j++;
  115.            if(((AND == 1) && ((r3 & endposition) == endposition)) ||                           ((AND == 0) && (r3 & endposition)) ^ INVERSE )
  116.                { 
  117.                  if(FILENAMEONLY) {
  118.                     num_of_matched++;
  119.                     printf("%s\n", CurrentFileName);
  120.                     return; }
  121.                  print_end = i - D_length - 1;
  122.                  if(!(lasti >= Max_record+num_read - 1))
  123.                     output(buffer, lasti, print_end, j);
  124.                }
  125.            lasti = i - D_length ;
  126.            TRUNCATE = OFF;
  127.            r2 = r3 = r1 = Init[0]; 
  128.            r1 = r_Init1 & r2;
  129.            r3 = ((( r2 >> 1) & CMask) | r1 ) & D_Mask;
  130.        }   
  131.     }
  132.     ResidueSize = num_read + Max_record - lasti;
  133.     if(ResidueSize > Max_record) {
  134.             ResidueSize = Max_record;
  135.             TRUNCATE = ON;   
  136.     }
  137.     strncpy(buffer+Max_record-ResidueSize, buffer+lasti, ResidueSize);
  138.     lasti = Max_record - ResidueSize;
  139.     if(lasti < 0) {
  140.        lasti = 1;
  141.     } 
  142.   }
  143.   return;
  144. }
  145.  
  146. fill_buf(fd, buf, record_size)
  147. int fd, record_size; unsigned char *buf;
  148. {
  149. int num_read=1;
  150. int total_read=0;
  151.     while(total_read < record_size && num_read > 0) {
  152.         num_read = read(fd, buf+total_read, 4096);
  153.         total_read = total_read + num_read;
  154.     }
  155.     return(total_read);
  156. }
  157.  
  158.